package com.freedy.dataStructure.search;

import com.freedy.dataStructure.sort.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Freedy
 * @date 2021/3/23 10:42
 */
public class FibonacciSearch {
    public static int maxSize = 100;
    public static int count = 0;
    public static void main(String[] args) {
        Test.MAX_TEST_DATA = 10;
        int[] ints = Test.randomArrMaker();
        ints[4] = 15;
        ints[5] = 15;
        ints[6] = 15;
        Arrays.sort(ints);
        System.out.println(Arrays.toString(Search(ints, 15)));
        System.out.println(count);
    }

    /**
     * 使用非递归方式
     */
    public static int[] Search(int[] arr, int key) {
        int low=0;
        int height= arr.length-1;
        int k=0;
        int mid=0;
        int[] fib = fib();
        while (height-low>fib[k]-1){
            k++;
        }
        int[] fibArr = Arrays.copyOf(arr, fib[k]);
        for (int i = height+1; i < fibArr.length; i++) {
            fibArr[i]=Integer.MAX_VALUE;
        }
        //只要条件满足就一直找
        while (low<=height){
            count++;
            mid=low+fib[k-1]-1;
            if (key<fibArr[mid]){
                height=mid-1;
                k-=1;
            }else if (key>fibArr[mid]){
                low=mid+1;
                k-=2;
            }else {
                if (mid<height){
                    int lIndex = mid;
                    int rIndex = mid + 1;
                    List<Integer> list = new ArrayList<>();
                    while (lIndex >= low && arr[lIndex] == key) {
                        list.add(lIndex);
                        lIndex--;
                    }
                    while (rIndex <= height && arr[rIndex] == key) {
                        list.add(rIndex);
                        rIndex++;
                    }
                    return list.stream().mapToInt(Integer::intValue).toArray();
                }else {
                    return new int[]{height};
                }
            }
        }
        return new int[]{-1};
    }


    /**
     * 得到一个斐波那契数列
     */
    public static int[] fib() {
        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }
}
